package com.practice.dp;

/**
 *  There are n coins in a line. (Assume n is even). Two players take turns 
 *  to take a coin from one of the ends of the line until there are no more 
 *  coins left. The player with the larger amount of money wins.
 *  
 *  Assume that you go first, describe an algorithm to compute the maximum 
 *  amount of money you can win.
 *
 */
public class CoinsInLine {
	public int max(int[] a) {
		int N = a.length;
		int[][] p = new int[N+2][N+2];
		
		for (int gap=1; gap<N; gap+=2) {
			for (int i=1; i<=N-gap; i++) {
				int j = i + gap;
				int p1 = a[i-1] + Math.min(p[i+2][j], p[i+1][j-1]);
				int p2 = a[j-1] + Math.min(p[i][j-2], p[i+1][j-1]);
				p[i][j] = Math.max(p1, p2);
			}
		}
		
		return p[1][N];
	}
	
	public int max2(int[] a) {
		int N = a.length;
		int[] A = new int[N+2];
		for (int i=0; i<N; i++) {
			A[i+1] = A[i] + a[i];
		}
		A[N+1] = A[N];
		
		int[][] p = new int[N+2][N+2];
		for (int i=1; i<=N; i++) p[i][i] = a[i-1];
		
		for (int gap=1; gap<N; gap++) {
			for (int i=1; i<=N-gap; i++) {
				int j = i + gap;
				p[i][j] = A[j]-A[i-1] - Math.min(p[i+1][j], p[i][j-1]);
			}
		}
		
		return p[1][N];
	}
}
